package top.humbleyuan.backtrack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Author HumbleYuan
 * @Date 2020/5/18 18:28
 * @Des 组合总和
 */
public class LeetCode_39 {
    static List<List<Integer>> res = new ArrayList<>();

    public static void main(String[] args) {
        int[] candidates = {2,3,6,7};
        int target = 7;
        Arrays.sort(candidates);

        dfs(0, new ArrayList<>(), target, candidates);
        System.out.println(res);
    }


    public static void dfs(int sum, ArrayList<Integer> list,int target,int[] candidates) {
        if(sum == target) {
            res.add(new ArrayList<>(list));
            return;
        }

        for(int i = 0;i < candidates.length;i++) {
            sum += candidates[i];
            // 剪枝
            if(sum > target) {
                sum -= candidates[i];
                continue;
            }

            list.add(candidates[i]);

            /**
             * 这里构造新的数组；
             * 或者传newIndex,下一轮i从newIndex开始
             */
            int[] newInt = Arrays.copyOfRange(candidates, i, candidates.length);

            dfs(sum, list, target, newInt);

            //回溯
            sum -= candidates[i];
            list.remove(list.size() - 1);
        }
    }
}
